﻿/*
 * Author: Roy Scheefhals
 * Modified by Martijn Koopman
 * 
 * Growing Selection Blob Detection ( this version does not have recursion )
 * This class also fiters out wrong blobs ( has to be put into new class though )
 * */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Drawing;

namespace KentekenHerkenning
{
    public class NonRecursiveGrowingSelection
    {
        private VImage image;

        private byte[] inputpixels;
        private int[] pixelslabeled; // pixels 

        private int givenlabel;
        
        //arrays used for non recursive checking of all pixels
        private int[] ToCheck1x;
        private int[] ToCheck1y;

        private int[] ToCheck2x;
        private int[] ToCheck2y;

        private int amountToCheckList1;
        private int amountToCheckList2;

        private Blob curBlob;
        private List<Blob> bloblist;

       
        public  System.Drawing.Bitmap DoAlgorithm(System.Drawing.Bitmap sourceImage)
        {

            //initialize variables
            givenlabel = 0;
            amountToCheckList1 = 0;
            amountToCheckList2 = 0;

            ToCheck1x = new int[100000];
            ToCheck1y = new int[100000];

            ToCheck2x = new int[100000];
            ToCheck2y = new int[100000];

            curBlob = new Blob();
            bloblist = new List<Blob>();


            Stopwatch s1 = new Stopwatch();
            s1.Start();

            //Initialize input/output image
            image = new VImage(sourceImage);
            VImage output = new VImage(sourceImage.Width, sourceImage.Height);
            inputpixels = image.GrayPixels;
            pixelslabeled = new int[image.Height * image.Width];

            //Start the growing selection
            startGrowingSelection();

            s1.Stop();
            Debug.WriteLine("Growing selection took: " + s1.ElapsedMilliseconds);
            Debug.WriteLine("amount of blobs: " + bloblist.Count);

            // Filter small blobs
            List<Blob> smallBloblist = new List<Blob>();
            foreach (Blob blob in bloblist)
            {
                int blobWidth = blob.maxx - blob.minx;
                int blobHeight = blob.maxy - blob.miny;

                if (blobWidth > 130 && blobHeight > 30 && blobWidth > blobHeight)
                {
                    smallBloblist.Add(blob);
                }
            }

            // Draw blobs on image
            int colors = 256 * 256 * 256;
            int increment = 15;
            if (smallBloblist.Count != 0)
            {
                increment = colors / smallBloblist.Count;
            }

            for (int i = 0; i < pixelslabeled.Length; i++)
            {
                if (pixelslabeled[i] == 0)
                    continue;

                int x = i % output.Width;
                int y = i / output.Width;

                // There's a LOT of blobs
                output.SetSinglePixel(x, y, 0x0000FF);//increment * pixelslabeled[i]);
            }

            // foreach blob
            foreach (Blob blob in smallBloblist)
            {
                int blobWidth = blob.maxx - blob.minx;
                int blobHeight = blob.maxy - blob.miny;

                int blobCenterX = blob.minx + (blobWidth / 2);
                int blobCenterY = blob.miny + (blobHeight / 2);

                // Set initial corners 
                // because it might be possible that one of the divided segments has no pixels
                blob.topLeftX = blob.bottomLeftX = blobCenterX;
                blob.topRightX = blob.bottomRightX = blobCenterX;
                blob.topLeftY = blob.topRightY = blobCenterY;
                blob.bottomLeftY = blob.bottomRightY = blobCenterY;

                // Calculate corners ( BY MARTIJN KOOPMAN )
                double maxDistance = 0;

                // Calculate top left corner
                // For each pixel P where Px < blobCenterX && Py < blobCenterY  
                for (int y = blob.miny; y < blobCenterY; y++)
                {
                    for (int x = blob.minx; x < blobCenterX; x++)
                    {
                        int distanceX = blobCenterX - x;
                        int distanceY = blobCenterY - y;

                        if (pixelslabeled[y * image.Width + x] == blob.label)
                        {
                            double distance = distanceX + distanceY;// Math.Sqrt((Math.Pow(distanceX, 2) + Math.Pow(distanceY, 2)));
                            if (distance > maxDistance)
                            {
                                maxDistance = distance;

                                // remember pixel
                                blob.topLeftX = x;
                                blob.topLeftY = y;
                            }
                        }
                    }
                }

                // Calculate bottom left corner
                maxDistance = 0;
                for (int y = blobCenterY; y < blob.maxy; y++)
                {
                    for (int x = blob.minx; x < blobCenterX; x++)
                    {
                        int distanceX = blobCenterX - x;
                        int distanceY = y - blobCenterY;

                        if (pixelslabeled[y * image.Width + x] == blob.label)
                        {
                            double distance = distanceX + distanceY;// Math.Sqrt((Math.Pow(distanceX, 2) + Math.Pow(distanceY, 2)));
                            if (distance >= maxDistance)
                            {
                                maxDistance = distance;

                                // remember pixel
                                blob.bottomLeftX = x;
                                blob.bottomLeftY = y;
                            }
                        }
                    }
                }

                // Calculate top right corner
                maxDistance = 0;
                // for each pixel P where Px > blobCenterX && Py < blobCenterY
                for (int y = blob.miny; y < blobCenterY; y++)
                {
                    for (int x = blobCenterX; x < blob.maxx; x++)
                    {
                        int distanceX = x - blobCenterX;
                        int distanceY = blobCenterY - y;

                        if (pixelslabeled[y * image.Width + x] == blob.label)
                        {
                            double distance = distanceX + distanceY;// Math.Sqrt((Math.Pow(distanceX, 2) + Math.Pow(distanceY, 2)));
                            if (distance > maxDistance)
                            {
                                maxDistance = distance;

                                // remember pixel
                                blob.topRightX = x;
                                blob.topRightY = y;
                            }
                        }
                    }
                }

                // Calculate bottom right corner
                maxDistance = 0;
                // for each pixel P where Px > blobCenterX && Py > blobCenterY
                for (int y = blobCenterY; y < blob.maxy; y++)
                {
                    for (int x = blobCenterX; x < blob.maxx; x++)
                    {
                        int distanceX = x - blobCenterX;
                        int distanceY = y - blobCenterY;

                        if (pixelslabeled[y * image.Width + x] == blob.label)
                        {
                            double distance = distanceX + distanceY;// Math.Sqrt((Math.Pow(distanceX, 2) + Math.Pow(distanceY, 2)));
                            if (distance >= maxDistance)
                            {
                                maxDistance = distance;

                                // remember pixel
                                blob.bottomRightX = x;
                                blob.bottomRightY = y;
                            }
                        }
                    }
                }

                Debug.WriteLine("Blob: " + blob.ToString());
            }

            output.ApplyPixelChanges();
            
            List<Blob> FilteredBlobs = new List<Blob>();



            //Filter all the blobs to try to get one blob ( BY ROY SCHEEFHALS )
            foreach (Blob b in smallBloblist)
            {
                //Do not include blobs:
                //with Left side and right side corners too close together
                if (b.bottomLeftY - b.topLeftY < 15 || b.bottomRightY - b.topRightY < 15)
                {
                    continue;
                }

                //with the diagonal corners too close together
                if (b.bottomRightX - b.topLeftX < 100 || b.topRightX - b.bottomLeftX < 100)
                {
                    continue;
                }

                //the diagonal points too close together on the Y axel
                if (b.bottomRightY - b.topLeftY < 15 || b.bottomLeftY - b.topRightY < 15)
                {
                    continue;
                }

                //Filter wrong width height ratios
                //rechst en onder ... links en boven vergelijken
                double ratioRightBottom = (b.topRightX - b.topLeftX) / (b.bottomRightY - b.topRightY);
                if (ratioRightBottom > 8)// drop the blob with a too high ratio
                { 
                    continue;
                }

                double ratioLeftTop = (b.bottomRightX - b.bottomLeftX) / (b.bottomLeftY - b.topLeftY);
                if (ratioLeftTop > 8)// drop the blob with a too high ratio
                { 
                    continue;
                }

                //are the vertical/horizontal edges not parallel ?
                int leftEdgeDif = b.topLeftX - b.bottomLeftX;
                int rightEdgeDif = b.topRightX - b.bottomRightX;
                int difference = Math.Abs(leftEdgeDif - rightEdgeDif);
                Debug.WriteLine("blob: " + b.topLeftX + ", " + b.topLeftY + "\ndifference: " + difference + "\nwidth" + (b.maxx - b.minx));
                if (difference > (0.3 * (b.maxx - b.minx)))
                {
                    continue;
                }

                FilteredBlobs.Add(b);
            }

            //Draw bounding box around the max and min x and y
            //Draw polygon of the blob corners
            Graphics g = Graphics.FromImage(output.localImage);
            foreach (Blob b in FilteredBlobs)
            {
                g.DrawRectangle(Pens.Red, new Rectangle(b.minx, b.miny, b.maxx - b.minx, b.maxy - b.miny));

                Point topLeftCorner = new Point(b.topLeftX, b.topLeftY);
                Point bottomLeftCorner = new Point(b.bottomLeftX, b.bottomLeftY);
                Point topRightCorner = new Point(b.topRightX, b.topRightY);
                Point bottomRightCorner = new Point(b.bottomRightX, b.bottomRightY);

                //Draw the lines between the corners of the blob
                g.DrawLine(Pens.White, topLeftCorner, topRightCorner);
                g.DrawLine(Pens.White, topLeftCorner, bottomLeftCorner);
                g.DrawLine(Pens.White, topRightCorner, bottomRightCorner);
                g.DrawLine(Pens.White, bottomLeftCorner, bottomRightCorner);
            }



            return output.localImage;
        }


        private void startGrowingSelection()
        {
            givenlabel = 1;
            int curpixel;
            // process whole image
            for (int y = 1; y < image.Height - 1; y++)
            {
                for (int x = 1; x < image.Width - 1; x++)
                {
                    curpixel = (y * image.Width) + x;

                    // Is there a forground pixel that hasnt been processed yet ? 
                    if (inputpixels[curpixel] > 0 && pixelslabeled[curpixel] == 0)
                    {
                        //initialize the blob and give first pixel his label
                        pixelslabeled[curpixel] = givenlabel;
                        curBlob.amountOfPixels++;
                        curBlob.label = givenlabel;
                        curBlob.maxx = curBlob.minx = x;
                        curBlob.maxy = curBlob.miny = y;
                        // start growing blob detection
                        if (checkarea(givenlabel, x, y, 1) == true) // returns true is more pixels are left in the image
                        {
                            //start processing the list
                            processList(givenlabel);
                            //after processlist, the blob has been found
                        }
                        else // blob was only 1 pixel large
                        {
                            curBlob = new Blob();
                            continue;
                        }

                        if (curBlob.amountOfPixels < 1000) 
                        {
                            // 1000 pixels are few for a whole License plate. 
                            // this amount has to be tested though.
                            curBlob = new Blob();
                            continue;
                        }

                        //initialize for new blob
                        bloblist.Add(curBlob); 
                        curBlob = new Blob(); 
                        givenlabel++;
                    }
                }
            }
        }

        private void processList(int label)
        {
            Boolean ProcessablePixels;

            //main loop
            for (; ; )
            {
                ProcessablePixels = false;

                //process list 1
                for (int i = 0; i < amountToCheckList1; i++)
                {
                    ProcessablePixels = true;
                    checkarea(label, ToCheck1x[i], ToCheck1y[i], 2);
                }
                amountToCheckList1 = 0;

                // process list 2
                for (int i = 0; i < amountToCheckList2; i++)
                {
                    ProcessablePixels = true;
                    checkarea(label, ToCheck2x[i], ToCheck2y[i], 1);
                }
                amountToCheckList2 = 0;

                // both list were empty so there are no connecting pixels anymore ( get out of the main loop )
                if (ProcessablePixels == false)
                {
                    break;
                }
            }
        }

        private Boolean checkarea(int label, int startx, int starty, int insertToList)
        {
            // boolean to check if there are ANY new items to process
            Boolean changed = false;

            // check the 8 connected pixels around the startpixel
            for (int patchy = -1; patchy < 2; patchy++)
            {
                for (int patchx = -1; patchx < 2; patchx++)
                {
                    int curpixel = ((starty + patchy) * image.Width) + (startx + patchx);

                    // stay inside the picture
                    if ((startx + patchx) >= 0 &&
                        (startx + patchx) < image.Width &&
                        (starty + patchy) >= 0 &&
                        (starty + patchy) < image.Height)
                    {
                        //there is a foreground pixel without a label
                        if (pixelslabeled[curpixel] == 0 && inputpixels[curpixel] > 0)
                        {
                            pixelslabeled[curpixel] = label;
                            curBlob.amountOfPixels++;

                            // keep track of the bounding box for the blob
                            if ((startx + patchx) > curBlob.maxx)
                                curBlob.maxx = startx + patchx;
                            if ((startx + patchx) < curBlob.minx)
                                curBlob.minx = startx + patchx;

                            if ((starty + patchy) > curBlob.maxy)
                                curBlob.maxy = starty + patchy;
                            if ((starty + patchy) < curBlob.miny)
                                curBlob.miny = starty + patchy;

                            //insert to list that is NOT currently being processed
                            if (insertToList == 1)
                            {
                                ToCheck1x[amountToCheckList1] = startx + patchx;
                                ToCheck1y[amountToCheckList1] = starty + patchy;
                                amountToCheckList1++;
                            }
                            else
                            {
                                ToCheck2x[amountToCheckList2] = startx + patchx;
                                ToCheck2y[amountToCheckList2] = starty + patchy;
                                amountToCheckList2++;
                            }

                            changed = true;
                        }
                    }
                }
            }

            return changed;
        }
    }
}